package Leetcode.每日一题;

import java.util.*;

/**
 * @ClassName 下一个更大数1
 * @since: 2023/8/2 11:39
 * @auth: kirito
 * @description: 单调栈
 **/
public class 下一个更大数2 {
    public int[] nextGreaterElements(int[] nums) {
        int length = nums.length;
        int[] greaterElements = new int[length];
        Arrays.fill(greaterElements, -1);
        int appendedLength = length * 2 - 1;
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = 0; i < appendedLength; i++) {
            int num = nums[i % length];  // i%length 第i个数
            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                greaterElements[stack.pop()] = num;
            }
            stack.push(i % length);
        }
        return greaterElements;
    }
}
